A:
大意:
构造一个长度为n,数值>0,每一位没有0且每一位数都不能被本身整除的数
分析:
本题还是好做,我的构造方式是“777.......57”,这样可以保证整个数做7的除法等价于最后两位数做7的除法,这样是一定不能整除的。
代码:https://codeforces.com/contest/1326/submission/73678676
B:
大意:
Alice有一条序列A[1~n],定义Xi = max(0,a1,a2,.....,ai-1);再定义一个新的序列Bi = Ai - xi,题目输入B序列,要求你输出原来的A序列。
分析:
首先x表示的就是在第i位之前前缀max数组,既然已知B,我们可以反推A。
我们先从第一位开始,由于第一位是定义的x1 = 0,所以A1 = B1;
第二位x2 = max(0,a1),A2 = B2 + X2,这里X2可以求出来;
第k位xk = max(0,a1,a2,....,ak-1),Ak = Bk + xk,这里的xk就是前面所有的最大值;
所以对于x的取值我们只要写一个递推关系式,记录前面的最大值就可以了,而B又是已知条件,所以A序列就可以直接递推求出来了。
代码:https://codeforces.com/contest/1326/submission/73673855
C:
大意:
给你一个1~n n个数的排列和一个正数k(1 <= k <= n),现在你要把整个排列划分成k个区间,要求每个区间不能有相交的地方。现在定义整个划分方式的得分是:k个区间中,所有最大值的和;答案输出这个最大值以及能得到最大分数的所有方案数,注意由于数很大,所以要对998244353取模。
分析:
首先题目是要求最大的得分和这种得分的划分方案数有多少种,所以我们先来想怎么能得到最大得分:
因为得分是划分了k个区间,所有k个区间里最大的值的和,所以满足最大得分的方案必须是把区间内:n || n - 1 || ...... || n - k + 1这样的数给划分开,所以最大的数值答案肯定就是这些数求个和就得到了。
其次,对于每一个划分点而言,两个连续的划分点中间的位置你都是可以移动的,因为两个连续的划分点中间的数肯定都是不满足上面所需的最大的数的,所以如果你把它们也放进区间里头去,实际上整个区间的最大值还是你刚刚找到的那个值,不会影响整体的方案(除非你走到另外一个区间里),因此方案数的差异就在这里,对于两个连续的划分线来说,他们两个贡献于答案的方案数是后面的下标-前面的下标(中间还有多少个位置可以放再加上本身的自己的贡献为1,所以就是后面的下标减前面的),根据乘法原理,最终整个答案就应该是所有这样的方案数相乘,不过要注意取模。
代码:https://codeforces.com/contest/1326/submission/73750468
D:
大意:
有一条序列S,要求你构造一个回文序列T,构造限制有:
①T不能比S长
②T = a+b,其中a是S的前缀,b是S的后缀,两者均可以为空且不需要是回文的。
输出最长的能构造出的T
分析:
T是a+b组成的,而ab必须是S的前后缀,我们发现这是一个非常强的条件,限制很大。在这个限制下我们可以初步的分解这个问题到两步:
①从S的两边分别选取相同的字母,一对一对的选取,左边和右边最终可以获得的分别记为l & r。
②两边取完之后,中间剩下的字母里,看有没有左边连续的回文序列或右边连续的回文序列,记为w。
也就是这样一个选法:
最后答案显然是l + w(取左右长度更大者) + r。
第一步很好做,直接匹配就可以了;第二步就不太好做了。
根据回文序列的特点,我们先把中间的串(记作k)做成k + '#' + 反k,那么现在问题就是求以最后一个字母为结尾的某个后缀序列,能和一个前缀序列匹配的最长长度的对应的序列是什么:
例如k = "dfdce",这里处理了之后K = "dfdce#ecdfd",就是求一个后缀和前缀相等的最长的是谁就行了,那么这里可以用KMP来求:next数组的定义就是一个前缀和一个非前缀的匹配,假设K的长度是n的话,那么next[n]的意义就是[1 ~ next[n]] === [n - next[n] + 1,n],就是我们要求的问题,最后输出substr就可以了。
代码:https://codeforces.com/contest/1326/submission/73854324
E:
大意:
一数字全排列P,长度为n;另一数字全排列Q,长度也为n。现在要将数列P顺次的加入一个答案序列,并且数字排列P中某些位置上会有炸弹,如果新加入的某个数位置上有炸弹,则会把整个序列中最大的数删去(炸弹触发的事件在加数之后)。现对于整个排列Q,求在从没有炸弹,到一个一个加入Q1 Q2 Q3...Qn-1,这n个情况的每一个的最终序列中最大的数组成的答案序列。
分析:
根据题目样例的答案可以猜到第一个性质:
性质①:整个答案序列是不上升序列
证明:假设整个答案序列中出现了一个相对上升的答案,则其与炸弹触发删去最大的数的条件矛盾:炸弹如果在这个数之后,显然会被炸掉;若其之后没有炸弹,那么前面的答案不可能比当前这个答案小,矛盾。因此整个答案序列中不可能出现一个相对上升的答案,于是整个答案序列是不上升序列。
性质①启发我们:整个答案是具有不上升性质的,这可以记录一个当前答案x,并且再挖掘一个跟x相关的性质,也就是关于x什么时候会下降的问题,如下有另一性质:
性质②:对于当前答案x,它能延续到下一位的条件是当且仅当其后>=x的数大于其后炸弹的数量。
实际上第二个性质也是比较显然的,当前的答案x想要不被删掉肯定要后面的数替他被炸掉。
于是到这里实际上就可以逐步的抽象这个问题了,我们要做这样几种操作:
①我们要知道一个位置上,其后有多少个数是>=它的,以及其后有多少个炸弹
②我们要能求出一个全局的最大值,即所有位置上>=当前这个位置数的个数去减掉之后炸弹的个数的最大值是多少,如果这个最大值都<=0,则说明当前答案必须要减少了,否则当前答案可以保留。
在抽离了整个问题到上面两个步骤之后,就可以知道这个题是用线段树来维护的:区间修改和区间查询最大值问题了;不过在打线段树之前,还需要想清楚区间怎么做的:我们对所有序列P中的元素做一个反映射,即w[p[i]] = i,用当前的值得到当前的位置,比如最开始的答案肯定是n(最开始是没有炸弹的),于是就说明从1n这个数所在序列中的位置这些数都有个特点:后面肯定有个数是>=它的(倒序查找),于是整个区间+1即可;其次对于炸弹的加入就简单一些,直接对区间1Q[i]做-1操作即可。
而全局最大值,查询根节点的信息就可以了。
至此整个问题就分析清楚了,具体问题看代码即可。
代码:https://codeforces.com/contest/1326/submission/73968973
